import java.util.*;

public class palindrome {
  /*public static boolean isPalindrome(String str) {
    int len = str.length();
    for (int i = 0; i <= len / 2; i++) {
      if (str.charAt(i) != str.charAt(len - 1 - i)) {
        return false;
      }
    }
    return true;
  }*/
  static Map <String, Boolean> map= new HashMap<String,Boolean>();
  public static boolean isPalindrome(String s){
    if(map.containsKey(s)) return map.get(s);
    int i = 0,j=s.length()-1;
    while(i<j)
      if(s.charAt(i++)!=s.charAt(j--)){
        map.put(s, false);
        return false;
      }
    map.put(s,true);
    return true;
  }
  public static int minCut(String s) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int len = s.length();
    if (len == 0 || isPalindrome(s)) return 0;
    
    // <K, V> = <Index, Count>
    int [] backtrackMap = new int[len];
    // Initialization
    /*for (int i = 0; i < len; i++) { 
      backtrackMap[i] = 0;
    }*/
    
    int tmp = 1024;
    for (int i = 1; i < len; i++) {
      for (int j = 0; j <= i; j++) {
        int cur = 0;
        if (isPalindrome(s.substring(j, i+1))) {
          if (j == 0) {
            cur = 0;
          } else {
            cur = backtrackMap[j-1] + 1;
          }
        } else {
          // if not a palindrome, then assign a large integer
          cur = 1024;
        }
        //System.out.println("For substring " + s.substring(j, i+1) + ", i = " + i + ", j = " + j + "; cur result is " + cur);
        if (cur < tmp) {
          tmp = cur;
        }
      }
      backtrackMap[i] = tmp;
      tmp = 1024;
    }
    
    return backtrackMap[len - 1];
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNext()) {
      String curLine = scanner.next();
      // System.out.println("Is " + curLine + " palidrome? " + isPalindrome(curLine));
      System.out.println(minCut(curLine));
    }
  }
}